#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution
{
public:
  int largestRectangleArea(vector<int> &heights)
  {
    unsigned long size = heights.size();
    if (size == 1)
    {
      return heights[0];
    }

    int res = 0;
    stack<int> stk;
    for (int i = 0; i < size; ++i)
    {
      while (!stk.empty() && heights[stk.top()] > heights[i])
      {
        int length = heights[stk.top()];
        stk.pop();
        int weight = i;
        if (!stk.empty())
        {
          weight = i - stk.top() - 1;
        }
        res = max(res, length * weight);
      }
      stk.push(i);
    }
    while (!stk.empty())
    {
      int length = heights[stk.top()];
      stk.pop();
      int weight = size;
      if (!stk.empty())
      {
        weight = size - stk.top() - 1;
      }
      res = max(res, length * weight);
    }
    return res;
  }
};

int main()
{
  vector<int> heights = {2, 1, 5, 6, 2, 3};
  Solution solute;
  cout << solute.largestRectangleArea(heights) << endl;
}